package org.basis.algorithm.lru;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 手写lru缓存，核心点：hash表 + 双向链表 实现增删改查时间复杂度O(1)
 * 假设缓存支持存储的key-value都是String类型的
 * 基于LinkedHashMap实现，这种方式就简单很多
 *
 * @author wenpan 2024/03/06 23:05
 */
public class LruCache2 {

    /**
     * 缓存容量
     */
    private final int cap;
    /**
     * 缓存
     */
    private LinkedHashMap<String, String> map = new LinkedHashMap<>();

    public LruCache2(int cap) {
        this.cap = cap;
    }

    public String get(String key) {
        if (!map.containsKey(key)) {
            return null;
        }
        String result = map.get(key);
        makeRecently(key);
        return result;
    }

    public void put(String key, String value) {
        // 如果不存在，则新增，新增时要判断下是否超出缓存容量
        if (!map.containsKey(key)) {
            if (cap <= map.size()) {
                // 移除一个最久未访问的元素
                removeFirst();
            }
        }
        // 覆盖value
        map.put(key, value);
        // 变为最近访问
        makeRecently(key);
    }

    /**
     * 将key变为最近访问
     */
    private void makeRecently(String key) {
        String result = map.get(key);
        // 删除key，然后重新插入到队尾
        map.remove(key);
        map.put(key, result);
    }

    private String removeFirst() {
        // 获取linkedList里的第一个元素
        String first = map.keySet().iterator().next();
        map.remove(first);
        return first;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (Map.Entry<String, String> entry : map.entrySet()) {
            builder.append("(").append(entry.getKey())
                    .append(",").append(entry.getValue()).append(")").append(",");
        }
        builder.append("]");
        return builder.toString();
    }

    public static void main(String[] args) {
        System.out.println('c' - 'a');
    }

}

